package com.chj.gaoji.class09;

public class Code03_MinCameraCover {

	public static class Node {
		public int value;
		public Node left;
		public Node right;
	}

	public static int minCameraCover1(Node root) {
		RetrunType1 data = process1(root);
		return (int) Math.min(data.uncovered + 1, Math.min(data.coveredNoCamera, data.coveredHasCamera));
	}

	// 潜台词：x是头节点，x下方的点都被覆盖的情况下
	public static class RetrunType1 {
		public long uncovered; // x没有被覆盖，x为头的树至少需要几个相机
		public long coveredNoCamera; // x被相机覆盖，但是x没相机，x为头的树至少需要几个相机
		public long coveredHasCamera; // x被相机覆盖了，并且x上放了相机，x为头的树至少需要几个相机

		public RetrunType1(long un, long no, long has) {
			uncovered = un;
			coveredNoCamera = no;
			coveredHasCamera = has;
		}
	}

	// 所有可能性都穷尽了
	public static RetrunType1 process1(Node X) {
		if (X == null) { // base case
			return new RetrunType1(Integer.MAX_VALUE, 0, Integer.MAX_VALUE);
		}

		RetrunType1 left = process1(X.left);
		RetrunType1 right = process1(X.right);
		// x uncovered
		// 左孩子： 左孩子没被覆盖，左孩子以下的点都被覆盖
		// 左孩子被覆盖但没相机，左孩子以下的点都被覆盖
		// 左孩子被覆盖也有相机，左孩子以下的点都被覆盖
		long uncovered = left.coveredNoCamera + right.coveredNoCamera;

		// x下方的点都被covered，x也被cover，但x上没相机
		long coveredNoCamera = Math.min(
				// 1)
				left.coveredHasCamera + right.coveredHasCamera,

				Math.min(
						// 2)
						left.coveredHasCamera + right.coveredNoCamera,

						// 3)
						left.coveredNoCamera + right.coveredHasCamera));

		// x下方的点都被covered，x也被cover，且x上有相机
		long coveredHasCamera = Math.min(

				left.uncovered, Math.min(left.coveredNoCamera, left.coveredHasCamera))

				+ Math.min(right.uncovered, Math.min(right.coveredNoCamera, right.coveredHasCamera))

				+ 1;

		return new RetrunType1(uncovered, coveredNoCamera, coveredHasCamera);
	}

	public static int minCameraCover2(Node root) {
		ReturnType2 data = process2(root);
		return data.cameras + (data.status == Status.UNCOVERED ? 1 : 0);
	}

	// 以x为头，x下方的节点都是被covered，x自己的状况，分三种
	public static enum Status {
		UNCOVERED, COVERED_NO_CAMERA, COVERED_HAS_CAMERA
	}

	// 以x为头，x下方的节点都是被covered，得到的最优解中：
	// x是什么状态，在这种状态下，需要至少几个相机
	public static class ReturnType2 {
		public Status status;
		public int cameras;

		public ReturnType2(Status status, int cameras) {
			this.status = status;
			this.cameras = cameras;
		}
	}

	public static ReturnType2 process2(Node root) {
		if (root == null) {
			return new ReturnType2(Status.COVERED_NO_CAMERA, 0);
		}
		ReturnType2 left = process2(root.left);
		ReturnType2 right = process2(root.right);
		int cameras = left.cameras + right.cameras;
		if (left.status == Status.UNCOVERED || right.status == Status.UNCOVERED) {
			return new ReturnType2(Status.COVERED_HAS_CAMERA, cameras + 1);
		}
		// 左右孩子，不存在没被覆盖的情况
		if (left.status == Status.COVERED_HAS_CAMERA || right.status == Status.COVERED_HAS_CAMERA) {
			return new ReturnType2(Status.COVERED_NO_CAMERA, cameras);
		}

		// 左右孩子，不存在没被覆盖的情况，也都没有相机
		return new ReturnType2(Status.UNCOVERED, cameras);
	}

//	// NO_CAMERA表示的是子节点没有相机，当前节点也没放相机
//	private final int NO_CAMERA = 0;
//	// HAS_CAMERA表示当前节点有一个相机
//	private final int HAS_CAMERA = 1;
//	// NO_NEEDED表示当前节点没有相机，但他的子节点有一个相机，把它给
//	// 覆盖了，所以它不需要了。或者他是一个空的节点也是不需要相机的
//	private final int NO_NEEDED = 2;
//
//	// 全局的，统计有多少相机
//	int res = 0;

//	public int minCameraCover(TreeNode root) {
//		// 边界条件判断
//		if (root == null)
//			return 0;
//		// 如果最后返回的是NO_CAMERA，表示root节点的子节点也没有相机，
//		// 所以root节点要添加一个相机
//		if (dfs(root) == NO_CAMERA)
//			res++;
//		// 返回结果
//		return res;
//	}
//
//	public int dfs(TreeNode root) {
//		// 如果是空的，就不需要相机了
//		if (root == null)
//			return NO_NEEDED;
//		int left = dfs(root.left), right = dfs(root.right);
//		// 如果左右子节点有一个是NO_CAMERA，表示的是子节点既没相机，也没相机覆盖它，
//		// 所以当前节点需要有一个相机
//		if (left == NO_CAMERA || right == NO_CAMERA) {
//			// 在当前节点放一个相机，统计相机的个数
//			res++;
//			return HAS_CAMERA;
//		}
//		// 如果左右子节点只要有一个有相机，那么当前节点就不需要相机了，否则返回一个没有相机的标记
//		return left == HAS_CAMERA || right == HAS_CAMERA ? NO_NEEDED : NO_CAMERA;
//	}

//作者：sdwwld
//链接：https://leetcode-cn.com/problems/binary-tree-cameras/solution/cong-xia-wang-shang-ji-suan-ji-bai-liao-100de-yong/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

}
